

//给定一个整数数组 nums 和一个正整数 k，找出是否有可能把这个数组分成 k 个非空子集，其总和都相等。 
//
// 
//
// 示例 1： 
//
// 
//输入： nums = [4, 3, 2, 3, 5, 2, 1], k = 4
//输出： True
//说明： 有可能将其分成 4 个子集（5），（1,4），（2,3），（2,3）等于总和。 
//
// 示例 2: 
//
// 
//输入: nums = [1,2,3,4], k = 3
//输出: false 
//
// 
//
// 提示： 
//
// 
// 1 <= k <= len(nums) <= 16 
// 0 < nums[i] < 10000 
// 每个元素的频率在 [1,4] 范围内 
// 
// Related Topics 位运算 记忆化搜索 数组 动态规划 回溯 状态压缩 
// 👍 522 👎 0


import java.util.Arrays;

/**
 * 698.划分为k个相等的子集.partition-to-k-equal-sum-subsets
 *
 * @author orz
 * @since 2022-03-30 16:03:41
 **/

class Solution_698 {
    public static void main(String[] args) {
        Solution solution = new Solution_698().new Solution();
        int[] array = new int[]{3522,181,521,515,304,123,2512,312,922,407,146,1932,4037,2646,3871,269};
        boolean b = solution.canPartitionKSubsets(array, 5);
        System.out.println(b);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {

        private int target;

        private boolean[] used;


        public boolean canPartitionKSubsets(int[] nums, int k) {
            used = new boolean[nums.length];
            //求和
            int sum = 0;
            for (int item : nums) {
                sum+=item;
            }

            //首先判断是否能被k整除
            if(sum % k > 0){
                return false;
            }

            //再判断最大数是否比桶中平均数还大
            target = sum / k;
            Arrays.sort(nums);
            if(nums[nums.length - 1] > target){
                return false;
            }

            return backtrack(nums,k,0);
        }

        /**
         *
         * @param nums 原始数组
         * @param k 子集数量
         * @param currentSum 当前计算的和
         */
        private boolean backtrack(int[] nums, int k, int currentSum) {
            if(k == 1){
                return true;
            }
            if(currentSum == target){
                //如果当前桶刚好装满了，就继续装下一个桶
                return backtrack(nums,k-1,0);
            }

            for(int i= nums.length -1;i>=0;i--){
                //如果当前已经用过了，就跳入下一个循环
                if(used[i]){
                    continue;
                }
                //判断装完之后是否大于target
                if(currentSum + nums[i] > target){
                    continue;
                }

                used[i] = true;
                //装完之后没有大于target，就继续往当前桶中装
                boolean result = backtrack(nums, k, currentSum + nums[i]);
                if(result){
                    return true;
                }
                //递归完成之后当前桶没符合要求的结果，就释放占用
                used[i] = false;
                while (i > 0 && nums[i] == nums[i-1]){
                    i--;
                }
            }
            return false;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}